package main;

import java.util.ArrayList;

import utils.Pair;
import utils.Processor;
import utils.Task;
import utils.Edge;

public class ListScheduler
{
	public static void schedule(ArrayList<Processor> processors,
	        ArrayList<Task> tasks, Integer[][] graph, boolean applyDuplication)
	        throws CloneNotSupportedException
	{
		// Find the processor which the task can be executed first at
		for(Task task : tasks)
		{
			Processor earliestProcessor = null;
			int taskStartTime = Integer.MAX_VALUE;
			
			Edge edge = null;

			Task dupParentTask = null;
			Pair<Integer, Edge> dupParentTaskInfo = null;

			// Compare base case with other cases to find the processor which is
			// ready first
			for(Processor processor : processors)
			{
				Pair<Integer, Edge> taskSTresultset = taskStartTime(task, processor, graph);
				int currentProcTaskStartTime = taskSTresultset.getFirst();

				Task tmpDupParentTask = null;
				Edge tmpDupEdge = null;
				Pair<Integer, Edge> tmpDupParentTaskInfo = null;
				boolean dupImproved = false;

				if(applyDuplication)
				{
					// checking if the parent task can be duplicated
					for(Task parentTask : task.getParents())
					{
						// when would the parent task start &
						// what would be the communication cost
						Pair<Integer, Edge> parentTaskSTresultset = taskStartTime(
						        parentTask, processor, graph);
						// how long would it take to prepare the current task on
						// the current processor &
						// what would be the highest communication cost. The
						// current parent is not included
						// into the preparation cost since they both are
						// supposed to be
						// scheduled on the same processor
						Pair<Integer, Edge> taskDataReadyTime = dataReadyTime(
						        task, processor, graph, parentTask);
						// when the task would start
						int taskSTDuplication = Math.max(
						        parentTaskSTresultset.getFirst()
						                + parentTask.getExecutionTime(),
						        taskDataReadyTime.getFirst());

						if(currentProcTaskStartTime > taskSTDuplication)
						{
							currentProcTaskStartTime = taskSTDuplication;
							tmpDupParentTaskInfo = parentTaskSTresultset;
							tmpDupParentTask = parentTask;
							
							tmpDupEdge = taskDataReadyTime.getSecond();
							
							dupImproved = true;
						}
					}
				}

				if(currentProcTaskStartTime < taskStartTime)
				{
					earliestProcessor = processor;
					taskStartTime = currentProcTaskStartTime;
					
					dupParentTask = tmpDupParentTask;
					dupParentTaskInfo = tmpDupParentTaskInfo;

					if(dupImproved)
					{
						edge = tmpDupEdge;
					}
					else
					{
						edge = taskSTresultset.getSecond();	
					}
				}
			}

			// duplicate one of parent tasks if necessary
			if(dupParentTask != null)
			{
				// Update & schedule task
				dupParentTask.setStartTime(earliestProcessor, dupParentTaskInfo.getFirst());
				earliestProcessor.scheduleTask(dupParentTask);
				scheduleEdge(dupParentTaskInfo.getSecond());
			}

			// Update & schedule task
			task.setStartTime(earliestProcessor, taskStartTime);
			earliestProcessor.scheduleTask(task);

			// Schedule the edge
			scheduleEdge(edge);
		}
	}
	
	private static void scheduleEdge(Edge edge)
	{
		if(edge != null && edge.getpSrc() != edge.getpDst())
		{
			edge.getpSrc().scheduleEdge(edge);
			edge.getpDst().scheduleEdge(edge);
		}
	}

	/*
	 * Compute start time for a task on a processor
	 */
	private static Pair<Integer, Edge> taskStartTime(Task task, Processor proc,
	        Integer[][] graph)
	{
		// Constraint: all parents have to be finished
		Pair<Integer, Edge> drtResultset = dataReadyTime(task, proc, graph, null);

		// Constraint: Both the processor and the data must be ready
		int taskST = Math.max(proc.getReadyTime(), drtResultset.getFirst());

		return new Pair<Integer, Edge>(taskST, drtResultset.getSecond());
	}

	/*
	 * Data Ready Time - earliest time a task can start execution on a processor
	 */
	private static Pair<Integer, Edge> dataReadyTime(Task task, Processor proc,
	        Integer[][] graph, Task parentTaskToExclude)
	{
		ArrayList<Task> parents = task.getParents();
		
		Edge latestEdge = null;

		// we want to start execute the task when the last parent finishes its
		// execution
		int maxEdgeFT = 0;

		// If no parents, then 0 is returned.
		for(Task parent : parents)
		{
			if(parentTaskToExclude == null || !parent.equals(parentTaskToExclude))
			{
				int comTime = 0;

				// compute edge finish time
				boolean parentIsScheduled = parent.isScheduled(proc);
				if(!parentIsScheduled)
				{
					comTime = graph[parent.getId()][task.getId()];
					
					// start time of parent node + execution time of parent node +
					// communication time to current node
					Pair<Integer, Processor> parentFinish = parent.fastestFinishingTime();
					if(parentFinish.getFirst() != null && parentFinish.getSecond() != null)
					{
						int edgeST = parentFinish.getFirst() + parent.getExecutionTime();
						int edgeFT = edgeST + comTime;

						// See if edge finish time is the largest one
						if(maxEdgeFT < edgeFT)
						{
							maxEdgeFT = edgeFT;

							latestEdge = new Edge();
							latestEdge.setpSrc(parentFinish.getSecond());
							latestEdge.setpDst(proc);
							latestEdge.setExecutionTime(comTime);
							latestEdge.setStartTime(edgeST);
						}	
					}		
				}	
			}
		}
		return new Pair<Integer, Edge>(maxEdgeFT, latestEdge);
	}

}
